package pro.softzhang.algo.lc100;

import java.util.*;

public class LC127_WordLadder {
    public static void main(String[] args) {

    }

    static class Solution {
        public int ladderLength(String beginWord, String endWord, List<String> wordList) {
            Queue<String> q1 = new LinkedList<>(), q2 = new LinkedList<>();
            Set<String> notVisited = new HashSet<>(wordList);
            int length = 1;
            q1.add(beginWord);
            while (!q1.isEmpty()) {
                String word = q1.remove();
                if(word.equals(endWord)) {
                    return length;
                }

                List<String> neighbors = getNeighbors(word);
                for (String neighbor : neighbors) {
                    if(notVisited.contains(neighbor)) {
                        q2.add(neighbor);
                        notVisited.remove(neighbor);
                    }
                }

                if(q1.isEmpty()) {
                    length++;
                    q1 = q2;
                    q2 = new LinkedList<>();
                }
            }
            return 0;
        }

        private List<String> getNeighbors(String word) {
            List<String> neighbors = new LinkedList<>();
            char[] chars = word.toCharArray();
            for (int i = 0; i < chars.length; i++) {
                char old = chars[i];
                for (char ch = 'a'; ch <= 'z'; ch++) {
                    chars[i] = ch;
                    neighbors.add(new String(chars));
                }
                chars[i] = old;
            }
            return neighbors;
        }
    }
}
